A computer instruction is the specification of an operation to be performed, and may include the address of one or more operands on which the operation will be performed, the address for the location of the results, and an address of the next instruction in the sequence. These specifications or addresses may be implicitly defined, that is the machine will assume, in the case of the specification of the next instruction location, that the instructions lie in sequence. That is, the next instruction is contained in the address following the location of the current instruction. The location of the current instruction is kept in a register called the sequential address register (SAR). During the execution of an instruction the SAR is advanced by one address unit.
In all systems that use SAR's, there must be an additional mechanism for initializing the value and for changing values at certain points in the program in order to execute subroutines, for example. This mechanism is a special instruction, called "branch." There are two basic kinds of branch instructions: a branch without stacking and a branch with stacking. Both types of branch cause a new value to be substituted for the next sequential address in the SAR and hence define the start of the location of a new sequence of instructions. A branch with stacking instruction causes the storage in a LIFO stack memory of the next sequential instruction address, before the original instruction sequence is altered, and can be used to execute a subroutine, for example. This enables the system to return to the original sequence at the stored address. For definitional purposes, the term "branch" as used herein will mean the branch with stacking operation.
After the completion of the subroutine operations following a branch instruction, the program should return to the point in the original instruction sequence which was the point of departure for the branch. This is accomplished by a "return instruction." The instruction address to which the program is to return must be stored at the time the branch instruction was executed. In order to accommodate several consecutive branch instructions, the last in-first out (LIFO) instruction address stack must be provided to store those return addresses.
The conventional way to provide an instruction address stack for a pipelined instruction architecture is to put a large, dedicated register file in the first stage of the instruction pipeline because this is the stage that determines the order of execution. However, with the advent of large-scale integrated circuitry, substantial reductions in unit cost can be achieved by condensing the instruction processing and arithmetic circuitry for the processor onto a single integrated circuit chip. However, the large storage functions of data storage and instruction storage must be carried out by separate memory chips since the available area on the processor chip is limited. Although it is desirable to maintain a record of return addresses for instruction branching which is immediately accessible by the first stage of the instruction pipeline, the inclusion of such a large storage function on the same integrated circuit chip containing the instruction and arithmetic processing elements, is not feasible. However, the placement of the return address storage function in the data storage could not be achieved in the prior art, even if the data storage were on the same integrated circuit chip, because a return address could not be accessed from the data store until several machine cycles or phases after the return instruction was read by the first stage.
The placement of last in-first out (LIFO) stacks in the data store of a data processing system is not new. For example, U.S. Pat. No. 4,041,462 to Davis, et al., assigned to the instant assignee, describes carrying out subroutine linkage by using an LIFO stack in the data storage. However Davis, et al, were not confronted with the concurrent pipelined instruction execution which is the problem to be solved for a sequential phase instruction pipeline. Davis, et al, have their instructions invoke the accessing of the stack in the data store. This would, of necessity, degrade the throughput of the instructions in an instruction pipeline.